Sau trận thua, Tyson đã hồi phục với hai trận thắng KO ngay từ hiệp 1 trước Henry Tillman [62] và Alex Stewart [63]. Chiến thắng của Tyson trước Tillman, huy chương vàng hạng nặng Olympic 1984, đã cho phép Tyson trả thù cho những trận thua khi còn nghiệp dư của mình trước Tillman. Những trận đấu này đã thiết lập một trận đấu loại để hướng tới trận đấu giành chức vô địch hạng nặng thế giới không thể tranh cãi, mà Evander Holyfield đã giành được từ Douglas trong lần bảo vệ danh hiệu đầu tiên.[64]

Tyson, người là ứng cử viên số một, phải đối mặt với ứng cử viên số hai Donovan "Dao cạo" Ruddock vào ngày 18 tháng 3 năm 1991, tại Las Vegas. Ruddock được xem là võ sĩ hạng nặng nguy hiểm nhất lúc đó và được cho là một trong những đối thủ nặng ký nhất. Tyson và Ruddock đã trả đòn qua lại trong hầu hết thời gian trận đấu, cho đến khi trọng tài Richard Steele ra quyết định gây tranh cãi dừng trận đấu vào hiệp thứ bảy có lợi cho Tyson. Quyết định này đã gây phẫn nộ cho người hâm mộ tham dự, gây ra một cuộc hỗn chiến trong đám đông khán giả. Trọng tài đã phải được hộ tống để thoát ra khỏi sàn đấu.[65]

Tyson và Ruddock đã gặp lại nhau vào ngày 28 tháng 6 năm đó, với việc Tyson hạ gục Ruddock hai lần và giành được quyết định nhất trí của trọng tài sau 12 vòng 113-109, 114-108 và 114-108.[66] Một cuộc chiến giữa Tyson và Holyfield cho chức vô địch không thể tranh cãi đã được lên kế hoạch vào ngày 8 tháng 11 năm 1991, tại Caesars Palace ở Las Vegas, nhưng Tyson đã phải rút lui sau khi bị chấn thương sụn sườn trong quá trình huấn luyện.[67]